public class No053 {
    /**
     * 统计一个数字在排序数组中出现的次数。
     */
    public int GetNumberOfK(int[] array, int k) {
        if (array.length == 0) return 0;
        int lo = GetFirstK(array, k);
        int hi = GetLastK(array, k);
        return hi - lo;
    }

    public int GetFirstK(int[] array, int k) {
        int lo = 0, hi = array.length - 1;
        int mid = lo + ((hi - lo) >> 1);
        while (lo <= hi) {
            if (array[mid] < k) {
                lo = mid + 1;
            } else hi = mid - 1;
            mid = lo + ((hi - lo) >> 1);
        }
        return lo;
    }

    public int GetLastK(int[] array, int k) {
        int lo = 0, hi = array.length - 1;
        int mid = lo + ((hi - lo) >> 1);
        while (lo <= hi) {
            if (array[mid] <= k) {
                lo = mid + 1;
            } else hi = mid - 1;
            mid = lo + ((hi - lo) >> 1);
        }
        return lo;
    }

    /**
     * 题目二：0 ~ n-1中缺失的数字。
     * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个
     * 数字都在范围0 ~ N-1之内。在范围0 ~ n-1内的n个数字中有且只有一个
     * 数字不在该数组中，请找出这个数字。
     */
    public int GetMissingNumber(int[] array) {
        if (array.length == 0) return 0;
        int lo = 0, hi = array.length - 1;
        int mid = lo + ((hi - lo) >> 1);
        while (lo <= hi) {
            if (array[mid] == mid) {
                lo = mid + 1;
            } else hi = mid - 1;
            mid = lo + ((hi - lo) >> 1);
        }
        return lo;
    }

}
